package ways;

import java.util.Arrays;

public class Solution {
//    public static final int MOD = (int) 1e9 + 7;
//    public int ways(String[] pizza, int k) {
//        // dp dp[][][]
//        int m = pizza.length, n = pizza[0].length();
//        var memo = new int[k][m][n];
//        for (int i = 0; i < k; i++)
//            for (int j = 0; j < m; j++)
//                Arrays.fill(memo[i][j], -1);
//        MatrixSum ms = new MatrixSum(pizza);
//        return dfs(k-1,0,0,ms,pizza.length,pizza[0].length(),memo);
//    }
//    private int dfs(int k,int i,int j,MatrixSum ms,int m,int n,int[][][] memo){
//        if (k == 0) // 递归边界：无法再切了
//            return ms.query(i, j, m, n) > 0 ? 1 : 0;
//        if (memo[k][i][j] != -1) // 之前计算过
//            return memo[k][i][j];
//        int res = 0;
//        for (int j2 = j + 1; j2 < n; j2++) // 垂直切
//            if (ms.query(i, j, m, j2) > 0) // 有苹果
//                res = (res + dfs(k - 1, i, j2, ms, m, n,memo)) % MOD;
//        for (int i2 = i + 1; i2 < m; i2++) // 水平切
//            if (ms.query(i, j, i2, n) > 0) // 有苹果
//                res = (res + dfs(k - 1, i2, j, ms, m, n,memo)) % MOD;
//        return memo[k][i][j] = res; // 记忆化
//    }
//    class MatrixSum {
//        private final int[][] sum;
//
//        public MatrixSum(String[] matrix) {
//            int m = matrix.length, n = matrix[0].length();
//            sum = new int[m + 1][n + 1];
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (matrix[i].charAt(j) & 1);
//                }
//            }
//        }
//
//        // 返回左上角在 (r1,c1) 右下角在 (r2-1,c2-1) 的子矩阵元素和（类似前缀和的左闭右开）
//        public int query(int r1, int c1, int r2, int c2) {
//            return sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1];
//        }
//    }
  //  public int ways(String[] pizza, int k) {
        // 动态规划
        // dp[i][j][k] 表示切把第i行第j列右下角的蛋糕分给k个人
//        int mod = 1_000_000_007;
//        int m = pizza.length;
//        int n = pizza[0].length();
//        apples = new int[m+1][n+1]; // 坐标(i,j)右下角的苹果数
//        int[][][]dp = new int[k+1][m][n];
//        for (int i = m-1; i >=0 ; i--) {
//            for (int j = n-1; j >=0 ; j--) {
//                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i].charAt(j) == 'A' ? 1 : 0); // 初始化apple数组
//                dp[i][j][1] = apples[i][j]>0?1:0;
//            }
//        }
//        for (int c = 2; c <= k; c++) {
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    // 水平方向切
//                    for (int i2 = i+1; i2 < m; i2++) {
//                       int apple = apples[i][j] - apples[i2][j]; // 保证分出去的有苹果
//                       if(apple>0){
//                           dp[i][j][c] = (dp[i][j][c] + dp[i2][j][c-1]%mod); // 如果分出去的那部分满足条件 也就是 把第i行第j列分给k个人 就是把第i2行第j列分给k-1个人
//                       }
//                    }
//                    // 竖直方向切
//                    for (int j2 = j+1; j2 < n; j2++) {
//                        int apple = apples[i][j] - apples[i][j2];
//                        if(apple>0){
//                            dp[i][j][c] = (dp[i][j][c] + dp[i][j2][c-1]%mod);
//                        }
//                    }
//                }
//            }
//        }
//        return dp[k][0][0];
 //   }

    private static final int MOD = (int)1e9+7;
    public int ways(String[] pizza, int k) {
        // dp
        int m = pizza.length;
        int n = pizza[0].length();
        int[][][] dp = new int[m][n][k+1]; // 表示第(i,j)右下角分成c块有多少种分法
        int[][] apples = new int[m+1][n+1]; // 二维数组后缀和
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                apples[i][j] = apples[i+1][j] + apples[i][j+1] - apples[i+1][j+1] + (pizza[i].charAt(j) == 'A'?1:0);
                dp[i][j][1] = apples[i][j]>0?1:0;// 初始化分成一块的情况
            }
        }
        for (int c = 2; c <= k; c++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 横着分
                    for (int i2 = i+1; i2 < m; i2++) {
                        if(apples[i][j]>apples[i2][j]){
                            dp[i][j][c] = (dp[i][j][c] + dp[i2][j][c-1])%MOD;
                        }
                    }
                    // 竖直分
                    for (int j2 = j+1; j2 < n; j2++) {
                        if(apples[i][j]>apples[i][j2]){
                            dp[i][j][c] = (dp[i][j][c] + dp[i][j2][c-1])%MOD;
                        }
                    }
                }
            }
        }
        return dp[0][0][k];
    }


//    private static int[][] apples;
//    private static final int mod = (int)1e9+7;
//    private static long[][][] meno;
//    public int ways(String[] pizza, int k) {
//        int m = pizza.length;
//        int n = pizza[0].length();
//        apples = new int[m+1][n+1];
//        for (int i = m-1; i >=0 ; i--) {
//            for (int j = n-1; j >=0 ; j--) {
//                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i].charAt(j) == 'A' ? 1 : 0);
//            }
//        }
//        meno = new long[m][n][k+1];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                for (int l = 0; l <= k; l++) {
//                    meno[i][j][l] = -1;
//                }
//            }
//        }
//        return (int)dfs(0,0,k,m,n);
//    }
//    // 第i行第j列分给k个人
//    private long dfs(int i,int j,int k,int m,int n){
//        if(k == 1){
//            // 分给最后一个人
//            // 如果剩下的披萨里面有苹果的话就返回1 没有就返回0
//            return apples[i][j]>0 ? 1 : 0;
//        }
//        if(meno[i][j][k]!=-1){
//            return meno[i][j][k];
//        }
//        // 横着分
//        long res = 0;// 有多少种分法
//        for (int i2 = i+1; i2 <m ; i2++) {
//            if(apples[i][j] - apples[i2][j]>0){
//                res= (res + dfs(i2,j,k-1,m,n))%mod;
//            }
//        }
//        // 竖着分
//        for (int j2 = j+1; j2 < n; j2++) {
//            if(apples[i][j] - apples[i][j2]>0){
//                res = (res + dfs(i,j2,k-1,m,n))%mod;
//            }
//        }
//        meno[i][j][k] = res;
//        return res;
//    }
}
